
/**
 * Implements an unbalanced binary search tree.
 * Note that all "matching" is based on the compareTo method.
 * 
 * @author Mark Allen Weiss with modifications by Lewis and Jonathan Buttner
 * @version Mar 5, 2010
 * @param <T> is the type.
 */
public class BST < T extends Comparable < ? super T > >
{
	/**
	 * This is a binary node.
	 */
    protected BSTNode root;
    private T _dupItem;

    /**
     * Constructs an empty tree.
     */
    public BST()
    {
        root = null;
        _dupItem = null;
    }

    /**
     * Insert into the tree.
     * @param x the item to insert.
     * @throws DuplicateItemException if x is already present.
     * @return T is the duplicate object that already existed in the tree.
     * This method will return null if the item was insterted correctly.
     */
    public T insert(T x)
    {
    	T duplicate = null;
    	try
    	{
    		root = insert(x, root);
    		_dupItem = null;    		
    	}
    	catch ( DuplicateItemException e )
    	{
    		duplicate = _dupItem;
    		_dupItem = null;
    	}
    	return duplicate;
    }

    /**
     * Remove from the tree..
     * @param x the item to remove.
     * @throws ItemNotFoundException if x is not found.
     */
    public void remove(T x)
    {
		root = remove(x, root);
    }

    /**
     * Remove minimum item from the tree.
     * @throws ItemNotFoundException if tree is empty.
     */
    public void removeMin()
    {
		root = removeMin(root);
    }

    /**
     * Find the smallest item in the tree.
     * @return smallest item or null if empty.
     */
    public T findMin()
    {
        return elementAt(findMin(root));
    }
    
    /**
     * This method prints the tree inorder.
     * 
     * @return a string representatino of the tree.
     */
    public String printInorder()
    {
    	return root == null ? "" : root.printInOrder();
    }

    /**
     * Find the largest item in the tree.
     * @return the largest item or null if empty.
     */
    public T findMax()
    {
		return elementAt(findMax(root));
    }

    /**
     * Find an item in the tree.
     * @param x the item to search for.
     * @return the matching item or null if not found.
     */
    public T find(T x)
    {
        return elementAt(find(x, root));
    }

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty()
    {
        root = null;
    }

    /**
     * Test if the tree is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty()
    {
		return root == null ? true : false;
    }

    /**
     * Internal method to get element field.
     * @param t the node.
     * @return the element field or null if t is null.
     */
    private T elementAt(BSTNode t)
    {
        return t == null ? null : t.element;
    }

    /**
     * Internal method to insert into a subtree.
     * @param x the item to insert.
     * @param t the node that roots the tree.
     * @return the new root.
     * @throws DuplicateItemException if x is already present.
     */
    protected BSTNode insert(T x, BSTNode t)
    {
        if (t == null)
        {
            t = new BSTNode(x);
        }
        else if (x.compareTo(t.element) < 0)
        {
            t.left = insert(x, t.left);
        }
        else if (x.compareTo(t.element) > 0)
        {
            t.right = insert(x, t.right);
        }
        else
        {
        	_dupItem = t.element;
            throw new DuplicateItemException();
        }
        return t;
    }

    /**
     * Internal method to remove from a subtree.
     * @param x the item to remove.
     * @param t the node that roots the tree.
     * @return the new root.
     * @throws ItemNotFoundException if x is not found.
     */
    protected BSTNode remove(T x, BSTNode t)
    {
        if (t == null)
        {
            throw new ItemNotFoundException(x.toString());
        }
        if (x.compareTo(t.element) < 0)
        {
            t.left = remove(x, t.left);
        }
        else if (x.compareTo(t.element) > 0)
        {
            t.right = remove(x, t.right);
        }
        else if (t.left != null && t.right != null) // Two children
        {
		    t.element = findMin(t.right).element;
		    t.right = removeMin(t.right);
        }
        else
        {
            t = (t.left != null) ? t.left : t.right;
        }
        return t;
    }

    /**
     * Internal method to remove minimum item from a subtree.
     * @param t the node that roots the tree.
     * @return the new root.
     * @throws ItemNotFoundException if t is empty.
     */
    protected BSTNode removeMin(BSTNode t)
    {
        if (t == null)
        {
            throw new ItemNotFoundException();
        }
        else if (t.left != null)
        {
            t.left = removeMin(t.left);
            return t;
        }
        else
        {
            return t.right;
        }
    }    

    /**
     * Internal method to find the smallest item in a subtree.
     * @param t the node that roots the tree.
     * @return node containing the smallest item.
     */
    protected BSTNode findMin(BSTNode t)
    {
		if (t != null)
		{
			while (t.left != null)
			{
				t = t.left;
			}
		}
		return t;
    }

    /**
     * Internal method to find the largest item in a subtree.
     * @param t the node that roots the tree.
     * @return node containing the largest item.
     * 
     */
    private BSTNode findMax(BSTNode t)
    {
        if (t != null)
        {
            while (t.right != null)
            {	
                t = t.right;
            }
        }

        return t;
    }

    /**
     * Internal method to find an item in a subtree.
     * @param x is item to search for.
     * @param t the node that roots the tree.
     * @return node containing the matched item.
     */
    private BSTNode find(T x, BSTNode t)
    {
        while (t != null)
        {
            if (x.compareTo(t.element) < 0)
            {
                t = t.left;
            }
            else if (x.compareTo(t.element) > 0)
            {
                t = t.right;
            }
            else
            {
                return t;    // Match
            }
        }
        
        return null;         // Not found
    }
    
    /**
     * A basic node stored in an unbalanced binary search tree.
     * This class is not accessible outside of this package.
     * 
     * @author Weiss (with revisions by Lewis)
     * @param <T> is the type.
     */
    private class BSTNode
    {
        T element;
        BSTNode left;
        BSTNode right;

        /**
         * Creates a node with no children.
         * @param theElement the element to store in this node.
         */
        BSTNode(T theElement)
        {
            element = theElement;
            left = right = null;
        }
        
        /**
         * Print the tree rooted at this node using inorder traversal.
         */
        public String printInOrder()
        {
        	String theTree = "";
            if (left != null)
                theTree = left.printInOrder();
            //System.out.print(element);
            theTree += element.toString() + "\n";
            if (right != null)
            	theTree += right.printInOrder();
            return theTree;
        }
    }
}
